package leetcode;


import com.alibaba.fastjson.JSON;

/**
 * 对角线遍历
 */
public class LeetCode498 {
    public int[] findDiagonalOrder(int[][] matrix) {
        if (matrix.length == 0) return new int[0];
        int[] result = new int[matrix.length * matrix[0].length];
        int index = 0;
        // 先遍历一行
        for (int i = 0; i < matrix[0].length; i++) {
            int x = 0, y = i;
            int maxSize = getSize(x, y, matrix.length, matrix[0].length);
            for (int j = 0; j <= maxSize; j++) {
                if (i % 2 == 0) {
                    result[index + maxSize - j] = matrix[x][y];
                } else {
                    result[index + j] = matrix[x][y];
                }
                x++;
                y--;
            }
            index += maxSize + 1;
        }
        for (int i = 1; i < matrix.length; i++) {
            int x = i, y = matrix[0].length - 1;
            int maxSize = getSize1(x, y, matrix.length, matrix[0].length);
            for (int j = 0; j <= maxSize; j++) {
                if ((matrix[0].length - 1 + i) % 2 == 0) {
                    result[index + maxSize - j] = matrix[x][y];
                } else {
                    result[index + j] = matrix[x][y];
                }
                x++;
                y--;
            }
            index += maxSize + 1;
        }
        return result;
    }

    private int getSize(int x, int y, int maxX, int maxY) {
        maxX--;
        maxY--;
        return Math.min(Math.min(maxX, maxY), Math.min(maxX - x, y));
    }

    public int getSize1(int x, int y, int maxX, int maxY) {
        maxX--;
        maxY--;
        if (maxX > 0) {
            maxX--;
            x--;
        } else {
            maxY--;
            y--;
        }
        return Math.min(Math.min(maxX, maxY), Math.min(maxX - x, y));
    }


    public static void main(String[] args) {
        LeetCode498 leetCode498 = new LeetCode498();
        int[][] i = new int[][]{{1},{3},{5}};
        System.out.println(JSON.toJSONString(leetCode498.findDiagonalOrder(i)));
    }
}